package leetcode;

/**
 * 5. 最长回文子串
 * @author yujiafan
 * @version 1.0.0
 * @create 2022-12-13
 */
public class LeetCode5 {

    public static String longestPalindrome(String s) {
        int len = s.length();
        if(len < 2){
            return s;
        }
        char[] chars = s.toCharArray();
        int maxLength = 1;
        String maxStr = s.substring(0,1);
        boolean[][] arr = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            arr[i][i] = true;
        }
        for (int L = 2; L <= len; L++) {
            for (int i = 0; i < len; i++) {
                // 右边界
                int j = i + L - 1;
                // 右边界溢出
                if(j >= len) break;
                if(chars[i] != chars[j]) continue;
                if(j - i < 3){
                    arr[i][j] = true;
                } else {
                    arr[i][j] = arr[i+1][j-1];
                }
                int tempLength = j - i + 1;
                if(arr[i][j] && tempLength > maxLength){
                    maxLength = tempLength;
                    maxStr = s.substring(i,j + 1);
                }
            }
        }
        return maxStr;
    }

    public static void main(String[] args) {
        System.out.println(longestPalindrome("aacabdkacaa"));

    }
}
